// 322. 零钱兑换(返回最少硬币个数) 完全背包问题
// 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，
// 返回 -1 。

// 你可以认为每种硬币的数量是无限的。
// 输入：coins = [1, 2, 5], amount = 11
// 输出：3 
// 解释：11 = 5 + 5 + 1

// 思路：dp数组
// coins=[1,2,5] amount=120
// 拿一枚面值为 1 的硬币 + 总金额为 119 的最优解法的硬币数量
// 拿一枚面值为 2 的硬币 + 总金额为 118 的最优解法的硬币数量
// 拿一枚面值为 5 的硬币 + 总金额为 115 的最优解法的硬币数量
// - dp[120] = Math.min(dp[119] + 1, dp[118] + 1, dp[115] + 1);
// 所以 dp[i]=Math.min(dp[i],dp[i-coin]+1)
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
 var coinChange = function(coins, amount) {
     let dp=new Array(amount+1).fill(Infinity);
     for(let i=0;i<=amount;i++){
         for(let coin in coins){
             if(i-coin>=0){
                 dp[i]=Math.min(dp[i],dp[i-coin]+1)
             }
         }
     }
     return (dp[amount]==Infinity)?-1:dp[amount];
 }
// 完全背包 组合
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
 var coinChange = function(coins, amount) {
    let dp=new Array(amount+1).fill(Infinity);// 因为可能满足不了amount
    dp[0]=0;
    for(let i=0;i<coins.length;i++){// 组合问题先遍历物品再遍历背包
        for(let j=coins[i];j<=amount;j++){
            dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]);
        }
    }
    return dp[amount]===Infinity?-1:dp[amount];
 }

//  518. 零钱兑换 II(返回能凑成多少种) 完全背包问题 排列
//  给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 
//  请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 
//  假设每一种面额的硬币有无限个。 
 
//  题目数据保证结果符合 32 位带符号整数。
// 示例 1：

// 输入：amount = 5, coins = [1, 2, 5]
// 输出：4
// 解释：有四种方式可以凑成总金额：
// 5=5
// 5=2+2+1
// 5=2+1+1+1
// 5=1+1+1+1+1

 /**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    let dp=new Array(amount+1).fill(0)
    dp[0]=1;
    // 先遍历物品
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<=amount;j++){// 再遍历背包
            dp[j]+=dp[j-coins[i]];// 求的是组合数
        }
    }
    return dp[amount];
};